- Title
- On extremal graphs with bounded girth
- Creator
- Delorme, Charles; Flandrin, Evelyne; Lin, Yuqing; Miller, Mirka; Ryan, Joe
- Relation
- Electronic Notes in Discrete Mathematics Vol. 34, p. 653-657
- Publisher Link
- http://dx.doi.org/10.1016/j.endm.2009.07.110
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2009
- Description
- By the extremal number ex(n;t) = ex(n;{C₃,C₄,…,Ct}) we denote the maximum size (number of edges) in a graph of n vertices, n > t, and girth (length of shortest cycle) at least g ≥ t + 1. In 1975, Erdős proposed the problem of determining the extremal numbers ex(n;4) of a graph of n vertices and girth at least 5. In this paper, we consider a generalized version of this problem, for t ≥ 5. In particular, we prove that ex(n;6) for n = 29, 30 and 31 is equal to 45, 47 and 49, respectively.
- Subject
- extremal graph; extremal number; forbidden cycles; size; girth
- Identifier
- http://hdl.handle.net/1959.13/808406
- Identifier
- uon:7645
- Identifier
- ISSN:1571-0653
- Language
- eng
- Reviewed
- Hits: 2491
- Visitors: 2725
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|